//There are n children standing in a line. Each child is assigned a rating value
// given in the integer array ratings. 
//
// You are giving candies to these children subjected to the following requireme
//nts: 
//
// 
// Each child must have at least one candy. 
// Children with a higher rating get more candies than their neighbors. 
// 
//
// Return the minimum number of candies you need to have to distribute the candi
//es to the children. 
//
// 
// Example 1: 
//
// 
//Input: ratings = [1,0,2]
//Output: 5
//Explanation: You can allocate to the first, second and third child with 2, 1, 
//2 candies respectively.
// 
//
// Example 2: 
//
// 
//Input: ratings = [1,2,2]
//Output: 4
//Explanation: You can allocate to the first, second and third child with 1, 2, 
//1 candies respectively.
//The third child gets 1 candy because it satisfies the above two conditions.
// 
//
// 
// Constraints: 
//
// 
// n == ratings.length 
// 1 <= n <= 2 * 104 
// 0 <= ratings[i] <= 2 * 104 
// 
// Related Topics 贪心算法 
// 👍 570 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Candy
class P135Candy {
    public static void main(String[] args) {
        Solution solution = new P135Candy().new Solution();
        Assert.assertEquals(solution.candy(new int[]{1, 0, 2}), 5);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int candy(int[] ratings) {
            int n = ratings.length;
            int ret = 1;
            int inc = 1, dec = 0, pre = 1;
            for (int i = 1; i < n; i++) {
                if (ratings[i] >= ratings[i - 1]) {
                    dec = 0;
                    pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                    ret += pre;
                    inc = pre;
                } else {
                    dec++;
                    if (dec == inc) {
                        dec++;
                    }
                    ret += dec;
                    pre = 1;
                }
            }
            return ret;
        }


        public int candy1(int[] ratings) {
            int len = ratings.length;
            int sum = 0;
            int[] left = new int[len];
            int[] right = new int[len];
            for (int i = 0; i < len; i++) {
                if (i > 0 && ratings[i] > ratings[i - 1]) {
                    left[i] = left[i - 1] + 1;
                } else {
                    left[i] = 1;
                }
            }
            for (int i = len - 1; i >= 0; i--) {
                if (i < len - 1 && ratings[i] > ratings[i + 1]) {
                    right[i] = right[i + 1] + 1;
                } else {
                    right[i] = 1;
                }
                int max = Math.max(left[i], right[i]);
                sum += max;
            }
            return sum;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}